Grafos de dependencias
+ Espacio de iteraciones
do i = 2, N-1
do j = 1, N-2
1 A(i,j) = A(i,j-1) * 2
2 C(i,j) = A(i-2,j+1) + 1
enddo
enddo
(Gp:) 1
(Gp:) 2
(Gp:) A 2,-1
(Gp:) A 0,1
(Gp:) i
(Gp:) j
Dependencias
? Test de dependencias: únicamente para funciones lineales del índice del bucle.
(Gp:) do i = L1, L2
X(a*i+b) =
= X(c*i+d)
enddo
(Gp:) ?
(Gp:) L1
(Gp:) L2
(Gp:) i
(Gp:) a*i+b
(Gp:) c*i+d
i1 i2
(Gp:) d – b
(Gp:) MCD(c,a)
(Gp:) ? Z ? no hay depend.
? Paralelizar el código significa repartir tareas (iteraciones de un bucle) a procesadores. Pero hay que respetar las dependencias de datos.
El problema principal son las dependencias de distancia > 0, y sobre todo aquellas que forman ciclos en el grafo de dependencias.
? Siempre es posible ejecutar un bucle en P procesa-dores, añadiendo sincronización para respetar las dependencias de datos… … lo que no significa que siempre sea sensato hacerlo, pues hay que tener en cuenta el coste global: cálculo + sincronización (comunicación).
Dependencias
Paralelización de bucles
Objetivos:
? Repartir las iteraciones de un bucle entre los procesadores, para que se ejecuten “a la par”.
? Siempre que se pueda, que se ejecuten de manera independiente, sin necesidad de sincronizar (dependencias de distancia 0).
? En función de las características del sistema (comunicación, reparto de tareas…) intentar que las tareas tengan un cierto tamaño.
Paralelización de bucles
Objetivos:
? Tal vez sólo se pueda utilizar un número limitado de procesadores.
? Atención al rendimiento (p. e., problemas en la cache).
Objetivos:
? En los bucles de más de una dimensión, paralelizar aquella dimensión que minimice la necesidad de sincronización entre procesadores y aumente el tamaño de grano.
Paralelización de bucles
do i = 0, N-1
do j = 1, M-1
A(i,j) = A(i,j-1) + 1
enddo
enddo
(Gp:) P0
(Gp:) P1
(Gp:) P2
(Gp:) P3
Paralelización de bucles
(Gp:) P0
(Gp:) P1
(Gp:) P2
(Gp:) P3
do i = 0, N-1
do j = 1, M-1
A(i,j) = A(i,j-1) + 1
enddo
enddo
Objetivos:
? En los bucles de más de una dimensión, paralelizar aquella dimensión que minimice la necesidad de sincronización entre procesadores y aumente el tamaño de grano.
? Si todas las dependencias son de distancia 0, las iteraciones se pueden repartir como se quiera entre los procesadores.
? Si no es así:
? si todas las dependencias son hacia adelante, sincronizarlas mediante barreras.
? si van hacia adelante y hacia atrás, sincronizarlas punto a punto (contadores o vectores de eventos).
? intentar alguna transformación del bucle para llevar a distancia 0 las dependencias.
Bucles con y sin sincron.
Ejemplos
do i = 0, N-1
C(i) = C(i) * C(i)
A(i) = C(i) + B(i)
D(i) = C(i) / A(i)
enddo
doall i = 0, N-1
C(i) = C(i) * C(i)
A(i) = C(i) + B(i)
D(i) = C(i) / A(i)
enddoall
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) C, 0
(Gp:) A, 0
(Gp:) i=0 1 2 3
Ejemplos
do i = 1, N-1
C(i) = C(i) * C(i)
A(i) = C(i) + B(i)
D(i) = C(i-1) / A(i)
enddo
forall i = 1, N-1
C(i) = C(i) * C(i)
A(i) = C(i) + B(i)
BARRERA (…)
D(i) = C(i-1) / A(i)
endforall
(Gp:) i=1 2 3 4
(Gp:) barrera
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) C, 0
(Gp:) A, 0
(Gp:) C, 1
Ejemplos
do i = 1, N-1
C(i) = C(i) * C(i)
A(i) = C(i) + B(i)
D(i) = C(i-1) / A(i)
enddo
(Gp:) i=1 2 3 4
(Gp:) barrera
doall i = 1, N-1
C(i) = C(i) * C(i)
A(i) = C(i) + B(i)
enddoall
[ BARERRA (…) ]
doall i = 1, N-1
D(i) = C(i-1) / A(i)
enddoall
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) C, 0
(Gp:) A, 0
(Gp:) C, 1
Vectores de eventos
no ordena las dependencias
mucho espacio en memoria
Ejemplos
do i = 2, N-2
A(i) = B(i-2) + 1
B(i+1) = A(i-2) * 2
enddo
(Gp:) 1
(Gp:) 2
(Gp:) A,2
(Gp:) B,3
(Gp:) 1 1 1 . . .
2 2 2 . . .
1 1 1
2 2 2
(Gp:) i=2 3 4 5 6 7
doacross i = 2, N-2
wait (vB,i-3)
A(i) = B(i-2) + 1
post (vA,i)
wait (vA,i-2)
B(i+1) = A(i-2) * 2
post (vB,i)
enddoacross
Ejemplos
do i = 2, N-2
A(i) = B(i-2) + 1
B(i+1) = A(i-2) * 2
enddo
doacross i = 2, N-2
wait (vB,i-3)
A(i) = B(i-2) + 1
post (vA,i)
wait (vA,i-2)
B(i+1) = A(i-2) * 2
post (vB,i)
enddoacross
(Gp:) 1
(Gp:) 2
(Gp:) A,2
(Gp:) B,3
(Gp:) , 3
(Gp:) 12 13 14
22 23 24
15 16 17
25 26 27
…
(Gp:) P0 P1 P2
Ejemplos
do i = 2, N-2
A(i) = B(i-2) + 1
B(i+1) = A(i-2) * 2
enddo
(Gp:) 1
(Gp:) 2
(Gp:) A,2
(Gp:) B,3
(Gp:) 12 13 14
22 23 24
15 16 17
25 26 27
…
(Gp:) P0 P1 P2
doacross i = 2, N-2,3
A(i) = B(i-2) + 1
wait (KA, i-1)
post (KA)
B(i+1) = A(i-2) * 2
enddoacross
Contadores
ordena las dependencias
sin problemas de espacio en memoria
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
? En general, los bucles de dependencias siempre son problemáticos y hay que analizar detenidamente qué se gana y qué se pierde (coste de la sincronización, problemas de acceso a cache…).
(Gp:) 1
(Gp:) 2
(Gp:) C,1
(Gp:) D,2
> Alternativas para el ejemplo
— wait / post ??
— 3 procesos independientes ??
— ejecución serie ??
Ejemplos
Optimizaciones
0. Deshacer la definición de constantes y las variables de inducción.
1. Eliminar todas las dependencias que no son intrínsecas al bucle. Por ejemplo:
do i = 0, N-1
X = A(i) * B(i)
C(i) = SQRT(X)
D(i) = X – 1
enddo
doall i = 0, N-1
X(i) = A(i) * B(i)
C(i) = SQRT(X(i)) D(i) = X(i) – 1
enddoall
(Gp:) convertir X en una
variable privada
Optimizaciones
2. Fisión del bucle.
Si una parte del bucle hay que ejecutarla en serie, romper el bucle convenientemente y ejecutar lo que sea posible en paralelo.
do i = 1, N-1
A(i) = A(i-1) / 2
D(i) = D(i) + 1
enddo
do i = 1, N-1
A(i) = A(i-1) / 2
enddo
doall i = 1, N-1
D(i) = D(i) + 1
enddoall
Optimizaciones
3. Ordenar las dependencias (hacia adelante).
do i = 1, N-1
A(i) = D(i-1) / 2
D(i) = C(i) + 1
enddo
forall i = 1, N-1
D(i) = C(i) + 1
BARRERA (…)
A(i) = D(i-1) / 2
endforall
(Gp:) 1
(Gp:) 2
(Gp:) D, 1
(Gp:) 2………….1
2………1
2…….1
(Gp:) 1…2..
1…2..
1…2..
(Gp:) ??
Optimizaciones
4. Alinear las dependencias: peeling.
do i = 1, N-1
A(i) = B(i)
C(i) = A(i-1) + 2
enddo
(Gp:) 1
(Gp:) 2
(Gp:) A, 1
doall i = 1, N-2
A(i) = B(i)
C(i+1) = A(i) + 2
enddoall
C(1) = A(0) + 2
A(N-1) = B(N-1)
Optimizaciones
do i = 2, N-1
A(i) = B(i)
C(i) = A(i-1) + A(i-2)
enddo
(Gp:) 1
(Gp:) 2
(Gp:) A, 2
(Gp:) A, 1
C(2) = A(1) + A(0)
C(3) = B(2) + A(1)
doall i = 2, N-3
A(i) = B(i)
X(i+1) = B(i+1)
C(i+2) = X(i+1) + A(i)
enddoall
A(N-2) = B(N-2)
A(N-1) = B(N-1)
do i = 2, N-1
A(i) = B(i)
X(i) = B(i)
C(i) = X(i-1) + A(i-2)
enddo
(Gp:) 1’
(Gp:) 2
(Gp:) A, 2
(Gp:) X, 1
(Gp:) 1
Optimizaciones
5. Generar hilos independientes
do i = 0, N-3
A(i+1) = B(i) + 1
B(i+2) = A(i) * 3
C(i) = B(i+2) – 2
enddo
B(2) = A(0) * 3
C(0) = B(2) – 2
doall k = 0, 2
do i = pid, N-4, 3
A(i+1) = B(i) + 1
B(i+3) = A(i+1) * 3
C(i+1) = B(i+3) – 2
enddo
enddoall
A(N-2) = B(N-3) + 1
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) B,0
(Gp:) B,2
(Gp:) A,1
1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3 3
Optimizaciones
6. Minimizar la sincronización
do i = 2, N-1
B(i) = B(i) + 1
C(i) = C(i) / 3
A(i) = B(i) + C(i-1)
D(i) = A(i-1) * C(i-2)
E(i) = D(i) + B(i-1)
enddo
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) B,0
(Gp:) B,1
(Gp:) A,1
(Gp:) 4
(Gp:) 5
(Gp:) C,1
(Gp:) C,2
(Gp:) D,0
doacross i = 2, N-1
B(i) = B(i) + 1
C(i) = C(i) / 3
post (vC,i)
wait (vC,i-1)
A(i) = B(i) + C(i-1)
post (vA,i)
wait (vA,i-1)
D(i) = A(i-1) * C(i-2)
E(i) = D(i) + B(i-1)
enddoacross
(Gp:) 1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
(Gp:)
i=2
3
4
…
Optimizaciones
7. Tratamiento de bucles: intercambio.
(Gp:) do i
do_par j
(Gp:) do_par i
do j
(Gp:) do j
do_par i
(Gp:) do_par j
do i
Optimizaciones
Ejemplo:
do i = 1, N-1
do j = 0, N-1
A(i,j) = A(i-1,j) + 1
enddo
enddo
(Gp:) do i = 1, N-1
doall j = 0, N-1
A(i,j) = A(i-1,j) + 1
enddoall
enddo
(Gp:) j=0 1 2 3
(Gp:) i=1
2
3
4
Optimizaciones
Ejemplo:
(Gp:) doall j = 0, N-1
do i = 1, N-1
A(i,j) = A(i-1,j) + 1
enddo
enddoall
do i = 1, N-1
do j = 0, N-1
A(i,j) = A(i-1,j) + 1
enddo
enddo
(Gp:) j=0 1 2 3
(Gp:) i=1
2
3
4
Optimizaciones
8. Tratamiento de bucles: cambio de sentido.
(Gp:) j=0 1 2
(Gp:) i=1
2
3
4
do i = 1, 100
do j = 0, 2
A(i,j) = A(i,j) – 1
D(i) = A(i-1,j+1) * 3
enddo
enddo
do j = 2, 0, -1
doall i = 1, 100
A(i,j) = A(i,j) – 1
D(i) = A(i-1,j+1) * 3
enddoall
enddo
Optimizaciones
do j = 1, 2N-1
doall i = max(1,j-N+1), min(j,N)
A(i,j-(i-1)) = A(i-1,j-(i-1)) + A(i,j-1-(i-1))
enddoall
enddo
9. Skew
do i = 1, N
do j = 1, N
A(i,j) = A(i-1,j) + A(i,j-1)
enddo
enddo
Optimizaciones
10. Otras optimizaciones típicas
Aumento del tamaño de grano y reduccción del overhead de la paralelización.
– Juntar dos bucles en uno (¡manteniendo la semántica!): fusión.
– Convertir un bucle de dos dimensiones en otro de una sola dimensión: colapso o coalescencia.
…
Reparto de tareas / iterac.
? ¿Cómo se reparten las iteraciones de un bucle entre los procesadores?
Si hay tantos procesadores como iteraciones, tal vez una por procesador.
? Pero si hay menos (lo normal), hay que repartir.
El reparto puede ser:
estático: en tiempo de compilación.
dinámico: en ejecución.
Reparto de tareas / iterac.
? El objetivo: intentar que el tiempo de ejecución de los trozos que se reparten a cada procesador sea similar, para evitar tiempos muertos (load balancing).
? En todo caso, OJO con las dependencias (sincronización), el tamaño de grano, la localidad de los accesos y el coste del propio reparto.
Reparto de tareas / iterac.
? Planificación estática
Qué ejecuta cada procesador se decide en tiempo de compilación. Es por tanto una decisión prefijada.
Cada proceso tiene una variable local que lo identifica, pid [0..P-1].
Dos opciones básicas: reparto consecutivo y reparto entrelazado.
Reparto de tareas / iterac.
– No añade carga a la ejecución de los threads.
– Pero no asegura el equilibrio de la carga entre los procesos.
– Permite cierto control sobre la localidad de los accesos a cache.
? Consecutivo
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3
? Entrelazado
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
principio = pid * N/P
fin = (pid+1) * N/P – 1
do i = principio, fin
…
enddo
do i = pid, N, P
…
enddo
Reparto de tareas / iterac.
? Equilibrio en el reparto de carga
(Gp:) 1-20
(Gp:) 21-40
(Gp:) 41-60
(Gp:) 61-80
(Gp:) estático (fijo)
(Gp:) Tej
(Gp:) asignación dinámica de una nueva tarea
(Gp:) 1-10
(Gp:) 21-30
(Gp:) 11-20
(Gp:) 31-40
(Gp:) Tej
do i = 1, 80
if (A(i) > 0) calcular()
enddo
Reparto de tareas / iterac.
? Planificación dinámica
Para intentar mantener la carga equilibrada, las tareas se van escogiendo en tiempo de ejecución de un cola de tareas. Cuando un proceso acaba con una tarea (un trozo del bucle) se asigna un nuevo trozo.
Dos opciones básicas: los trozos que se van repartiendo son de tamaño constante o son cada vez más pequeños.
Reparto de tareas / iterac.
Las iteraciones se reparten una a una o por trozos
? Self / Chunk scheduling
Añade carga a la ejecución de los threads.
Hay que comparar ejecución y reparto.
LOCK (C);
mia = i;
i = i + Z; Z = 1 ? self
UNLOCK (C);
while (mia <= N-1)
endwhile
do j = mia, min(mia+Z-1, N-1)
…
enddo
LOCK (C)
mia = i;
i = i + Z;
UNLOCK (C)
Reparto de tareas / iterac.
Los trozos de bucle que se reparten son cada vez más pequeños según nos acercamos al final.
? Guided / Trapezoidal
? Guided : parte proporcional de lo que queda por ejecutar:
Zs = (N – i) / P (entero superior)
que equivale a:
Zi = Zi-1 (1 – 1/P)
Reparto de tareas / iterac.
? Trapezoidal: reduciendo el trozo anterior en una constante: Zi = Zi-1 – k
(Gp:) op. de planificación
(Gp:) Z1
(Gp:) Zn
(Gp:) 1
(Gp:) n
(Gp:) 2
(Gp:) i
(Gp:) k
(Gp:) Z2
Reparto de tareas / iterac.
? En general, el reparto dinámico busca un mejor equilibrio en el reparto de carga, pero:
– hay que considerar la carga que se añade (overhead), en relación al coste de las tareas que se asignan.
– hay que considerar la localidad en los accesos a los datos y los posibles problemas de falsa compartición.
Reparto de tareas / iterac.
? Ejemplo de reparto (1.000 iteraciones, 4 procesadores):
? chunk (Z = 100)
100 100 100 100 100 100 100 100 100 100 (10)
? guided
quedan: 1000 750 562 421 … 17 12 9 6 4 3 2 1
se reparten: 250 188 141 106 … 5 3 3 2 1 1 1 1 (22)
? trapezoidal (Z1 = 76, Zn = 4 >> k = 3)
76 73 70 67 … 16 13 10 7 4 (25)
Paralelismo de función
? Paralelismo a nivel de procedimiento o función:
(Gp:) F2
(Gp:) F3
(Gp:) F1
(Gp:) F4
(Gp:) F5
– modelo Fork / Join
– Parallel sections
Fork
F1
F2
Join
Fork
F3
F4
Join
F5
doall k = 0, 1
if (pid = 0) then F1
if (pid = 1) then F2
endoall
[barrera]
doall k = 0, 1
if (pid = 0) then F3
if (pid = 1) then F4
endoall
F5
? El objetivo de un sistema de P procesadores es ejecutar el código P veces más rápido.
? Problemas (algunos):
– ¿puede ejecutarse todo el código en paralelo? ¿está bien repartida la carga?
– ¿dónde están los datos? ¿cuál es el coste de la transmisión de datos?
– ¿cuál es el coste de la sincronización?
– ¿es eficiente el uso de la memoria cache?
Rendimiento
? Ejecución en un procesador (código serie, no la versión paralela de 1 procesador) ? Ts
Ejecución en P procesadores ? Tp
fa = Ts / Tp ? límite P
ideal: crecer linealmente con P
efic = fa / P ? límite 1
ideal: constante
Rendimiento
La parte más lenta (serie) en la ejecución de un pro-grama marcará la velocidad de ejecución del mismo.
Serie Ts ? Paralelo Ts / P
Parte en paralelo (f), pero parte en serie (1-f)
fa (speed-up) = Ts / Tp = Ts / (f*Ts/P + (1-f)Ts)
= 1 / (1-f) (máximo)
= independiente de P!
? ¿Es todo el código paralelizable? En general, no.
– Ley de Amdahl (tamaño constante)
Rendimiento
Rendimiento
– Ley de Gustafson (tiempo constante)
En muchos casos, se utiliza el paralelismo no para ir más rápido, sino para ejecutar tareas de mayor tamaño.
fa = (1-f) + f*p
(Gp:) f*Ts
(Gp:) (1-f)*Ts
(Gp:) f*Ts*p
(Gp:) (1-f)*Ts
(Gp:) (1-f)*Ts
(Gp:) mayor tamaño
(Gp:) p procesadores
(Gp:) f*Ts
Rendimiento
? A la fracción de código en paralelo, hay que añadirle una serie de overheads; por ejemplo, la comunicación debida al reparto o recolección de datos en unos casos y a la sincronización de procesos en otros.
(Gp:) T_ej
(Gp:) T_com
(Gp:) n. de procesadores
(Gp:) T_total
Tp = Ts / P + Tcom(P)
Rendimiento
? Load balancing
Otra fuente típica de perdida de eficiencia en la ejecución en paralela es el reparto no equilibrado de tareas.
Ejemplo: 6 tareas independientes, de peso equivalente,
? entre 3 procesadores Tp = Ts/3
? entre 4 procesadores Tp = Ts/3
Rendimiento
? No podemos olvidarnos de la memoria cache. Para que su uso sea eficiente, se necesita reutilizar los datos que se cargan (un bloque o line).
Por ejemplo, si A(1) y A(2) están en posiciones consecutivas de memoria, tal vez sea conveniente que se procesen en el mismo procesador para aumentar la tasa de aciertos de la cache.
? Por otra parte, todos los overheads que añada la ejecución paralela hay que valorarlos en función del tamaño de grano, es decir en relación al tiempo de ejecución.
Rendimiento
 Página anterior | Volver al principio del trabajo | Página siguiente  |